package Stack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class _726_NumberofAtoms {
    int pos = 0;
    String formula;
    public String countOfAtoms(String formula) {
        Map<String, Integer> atoms = new HashMap<>();
        this.formula = formula;
        atoms = helper();
        String[] sres = new String[atoms.size()];
        int sp = 0;
        for (Map.Entry<String, Integer> e : atoms.entrySet()) {
            sres[sp++] = e.getKey();
        }
        Arrays.sort(sres);
        String res = "";
        for (String s : sres) {
            res += s + (atoms.get(s) == 1 ? "":atoms.get(s));
        }
        return res;
    }

    public Map<String, Integer> helper() {
        Map<String, Integer> res = new HashMap<>();
        Stack<String> stacks = new Stack<>();
        while (pos < formula.length() && formula.charAt(pos) != ')') {
            char c = formula.charAt(pos);
            if (Character.isDigit(c)) {
                String digits = "" + c;
                pos++;
                //get all digits
                while (pos < formula.length() && Character.isDigit(formula.charAt(pos))) {
                    digits += formula.charAt(pos++);
                }
                String atom = stacks.pop();
                //add new atoms to the old map
                res.put(atom, res.getOrDefault(atom, 0) + Integer.parseInt(digits));
            } else if (Character.isUpperCase(c)) {
                if (!stacks.isEmpty()) {
                    String atom = stacks.pop();
                    //add new atoms to the old map
                    res.put(atom, res.getOrDefault(atom, 0) + 1);
                }
                String atom = ""+c;
                pos++;
                //get lowercase tail
                while (pos < formula.length() && Character.isLowerCase(formula.charAt(pos))) {
                    atom += formula.charAt(pos++);
                }
                stacks.push(atom);
            } else {
                if (!stacks.isEmpty()) {
                    String atom = stacks.pop();
                    //add new atoms to the old map
                    res.put(atom, res.getOrDefault(atom, 0) + 1);
                }
                //jump the begin parentheses
                pos++;
                //get the inner parentheses atoms' count
                Map<String, Integer> parentheses = helper();
                for (Map.Entry<String, Integer> e : parentheses.entrySet()) {
                    res.put(e.getKey(), res.getOrDefault(e.getKey(), 0) + e.getValue());
                }
            }
        }
        if (!stacks.isEmpty()) {
            String atom = stacks.pop();
            //add new atoms to the old map
            res.put(atom, res.getOrDefault(atom, 0) + 1);
        }
        if (pos < formula.length() && formula.charAt(pos) == ')') {
            pos++;
        }
        //get every atom's times
        if (pos < formula.length() && Character.isDigit(formula.charAt(pos))) {
            String time = "" + formula.charAt(pos++);
            //get all digits
            while (pos < formula.length() && Character.isDigit(formula.charAt(pos))) {
                time += formula.charAt(pos++);
            }
            int times = Integer.parseInt(time);
            for (Map.Entry<String, Integer> e : res.entrySet()) {
                res.put(e.getKey(), e.getValue()*times);
            }
        }
        return res;
    }
}
